package com.lq.learningTest.Tree;

import java.util.Stack;

//递归遍历二叉树
public class RecursiveBinaryTree {
    //使用内部类的方法
//    public static class Node {
//        public int value;
//        public Node left;
//        public Node right;
//
//        public Node(int v) {
//            value = v;
//        }
//    }
//
//
//    // 先序打印所有节点
//    public static void Preorder(Node root) {
//        if (root == null) {
//            return;
//        }
//        System.out.println(root.value);
//        Preorder(root.left);
//        Preorder(root.right);
//    }
//
//    public static void Inorder(Node root) {
//        if (root == null) {
//            return;
//        }
//        Inorder(root.left);
//        System.out.println(root.value);
//        Inorder(root.right);
//    }
//
//    public static void Postorder(Node root) {
//        if (root == null) {
//            return;
//        }
//        Postorder(root.left);
//        Postorder(root.right);
//        System.out.println(root.value);
//    }
//
//    public static void main(String[] args) {
//        Node root = new Node(1);
//        root.left = new Node(2);
//        root.right = new Node(3);
//        root.left.left = new Node(4);
//        root.left.right = new Node(5);
//        root.right.left = new Node(6);
//        root.right.right = new Node(7);
//
//
//        Preorder(root);
//        System.out.println("====先序遍历====");
//        Inorder(root);
//        System.out.println("====中序遍历====");
//        Postorder(root);
//        System.out.println("====后续遍历====");
//
//    }

    //使用堆栈的方法
    public static class Node {
        public int value;
        public Node left;
        public Node right;

        public Node(int v) {
            value = v;
        }
    }

    public static void pre(Node head) {
        //实现先序遍历
        System.out.print("pre-order: ");
        if (head != null) {
            Stack<Node> stack = new Stack<Node>();
            //入栈
            stack.add(head);
            while (!stack.isEmpty()) {
                //弹栈
                head = stack.pop();
                System.out.print(head.value + " ");
                if (head.right != null) {
                    stack.push(head.right);
                }
                if (head.left != null) {
                    stack.push(head.left);
                }
            }
        }
        System.out.println();
    }

    public static void main(String[] args) {
        Node root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(3);
        root.left.left = new Node(4);
        root.left.right = new Node(5);
        root.right.left = new Node(6);
        root.right.right = new Node(7);


        pre(root);
    }

}
